package cn.edu.njust.alg;

import java.util.Arrays;


public class KSelectImpl {
	
	public static void swap(int[] a, int p, int q) {

		int tmp = a[p];
		a[p] = a[q];
		a[q] = tmp;
	}
	
	public static int partion(int[] a, int begin, int end) {
		int key = a[begin];
		int p = begin;
		int q = end + 1;
		while (true) {
			while (a[++p] > key && p<end)
				;
			while (a[--q] < key)
				;
			if (p >= q)
				break;
			swap(a, p, q);
		}
		a[begin] = a[q];
		a[q]=key;
		
		return q;
	}
	
	public static int select(int[]a,int begin,int end,int k) {
		if(begin==end){
			return a[begin];
		}
		int p = partion(a, begin, end);
		int q = p-begin+1;
		if(k<=p){
			return select(a, begin, p, k);
		}else{
			return select(a, p+1, end, k-q);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = { 3, 45, 6, 78, 454, 23, 23, 747, 538, 453 };
		
		int s = select(a, 0, a.length-1, 3);
		System.out.println(s);
		Arrays.sort(a);
		for(int i:a){
			System.out.printf("%d ",i);
		}
		System.out.println();
	}

}
